/**
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 * <p>
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 * <p>
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3, k = 3
 * 输出："213"
 * 示例 2：
 * <p>
 * 输入：n = 4, k = 9
 * 输出："2314"
 * 示例 3：
 * <p>
 * 输入：n = 3, k = 1
 * 输出："123"
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 9
 * 1 <= k <= n!
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(getPermutation(3, 6));
    }

    /**
     * 用数学直接去算应该是最快的，比一个个算出来然后去找好
     *
     * @param n
     * @param k
     * @return
     */
    public static String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        boolean[] used = new boolean[n];
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }
        return getPermutation(n, used, factorial, k, sb);
    }

    /**
     * 递归下去算
     */
    public static String getPermutation(int n, boolean[] used, int[] factorial, int k, StringBuilder sb) {
        if (k == 1) {
            // 如果已经到了最后的匹配，从可以用的数字里面挑了放到答案里面
            for (int i = 0; i < n; i++) {
                if (!used[i]) {
                    sb.append(i + 1);
                }
            }
            return sb.toString();
        }
        // 在没有被使用的数字里面找到第start个数字
        int multi = factorial[n - 1 - sb.length()];
        int start = (int) Math.ceil((double) k / multi);
        for (int i = 0, tmp = start - 1; i < n; i++) {
            if (!used[i]) {
                // 如果没有被使用
                if (tmp-- == 0) {
                    // 如果找到了
                    used[i] = true;
                    sb.append(i + 1);
                    // 递归下去
                    if (sb.length() != n) {
                        // 根据用掉的数，算出来下一个k
                        return getPermutation(n, used, factorial, k - (start - 1) * multi, sb);
                    } else {
                        return sb.toString();
                    }
                }
            }
        }
        return sb.toString();
    }

}